/*
 * @lc app=leetcode.cn id=79 lang=cpp
 * @lcpr version=30204
 *
 * [79] 单词搜索
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    vector<pair<int, int>> directions{
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}};
    string cur;
    bool exist(vector<vector<char>> &board, string word)
    {
        if (board.size() <= 0 || board[0].size() <= 0)
            return false;
        vector<vector<bool>> visted(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                if (DFS(board, word, i, j, visted))
                {
                    return true;
                }
            }
        }
        return false;
    }

private:
    bool DFS(vector<vector<char>> &board, string &word, int x, int y, vector<vector<bool>> &visted)
    {
        if (cur.size() == word.size())
        {
            return cur == word;
        }
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || visted[x][y] || board[x][y] != word[cur.size()])
        {
            return false;
        }

        visted[x][y] = true;
        cur.push_back(board[x][y]);
        for (auto e : directions)
        {
            int nx = e.first + x;
            int ny = e.second + y;
            if (DFS(board, word, nx, ny, visted))
            {
                return true;
            }
        }
        cur.pop_back();
        visted[x][y] = false;
        return false;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]\n"ABCCED"\n
// @lcpr case=end

// @lcpr case=start
// [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]\n"SEE"\n
// @lcpr case=end

// @lcpr case=start
// [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]\n"ABCB"\n
// @lcpr case=end

 */
